package org.example.myleet.p658;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int targetId = binarySearchClosestId(arr, x);
        List<Integer> res = new ArrayList<>(k);
        int start = targetId - 1, end = targetId + 1, count = 1;
        while (count < k) {
            if (start < 0) {
                ++end;
            } else if (end > arr.length - 1) {
                --start;
            } else {
                if (Math.abs(arr[start] - x) <= Math.abs(arr[end] - x)) {
                    --start;
                } else {
                    ++end;
                }
            }
            ++count;
        }
        for (int i = start + 1; i < end; ++i) {
            res.add(arr[i]);
        }
        return res;
    }

    private int binarySearchClosestId(int[] arr, int target) {
        int l = 0, r = arr.length - 1, m;
        while (r - l > 1) {
            m = (l + r) >> 1;
            if (arr[m] == target) {
                return m;
            } else if (arr[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return (Math.abs(arr[l] - target) <= Math.abs(arr[r] - target)) ? l : r;
    }
}
